package chapter02;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses93 {
    /**
     * 回溯
     * process(s,chs,count,pos,sb)
     * 从chs或s下标为pos开始组合ip第count个整数 将组合加过加入sb中 count[0,4)
     * 递归出口
     * 1).字符串中数字全部组合并且ip的4个整数已经组合 将sb中字符串加入列表res
     *  if count==4&&pos==chs.length
     *      res.add(sb.toString())
     *      return
     * 2).字符串中数字全部组合但是count没有组合完 该种结果不符合要求 剪枝
     *  if pos==chs.length
     *      return
     * 3).ip中4个整数只能取值在[0,255] 一个整数的位数在[1,3]之间
     *  for length->[1,3] 整数位数
     *      当前截取的字符串 str=s.substring(pos,pos+length)
     *      if length<=2||Integer.parseInt(str)<=255 限制整数范围
     *          整数之间需要"." 即除了第一个整数 之后整数最前方有个"."
     *          sb.append(count>0?"."+str:str)
     *          process(s,chs,count+1,pos+length,sb) 从s或chs下标为pos+length讨论第count+1个整数的组合
     *          int strLen=sb.length()
     *          sb.delete(count>0?strLen-length-1:strLen-length,strLen) 除去sb本次组合的整数值 进行整数位数length+1的组合
     *          特别要求整数不能有前导0 因此遇到整数开头是0 本次整数只能是0 后续组合都不符合要求 剪枝
     *          if chs[pos]=='0'
     *             return
     */
    List<String> res =new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        char[] chs=s.toCharArray();
        process(s,chs,0,0,new StringBuffer());
        return res;
    }

    public void process(String s,char[] chs,int count,int pos,StringBuffer sb){
        if(count==4&&pos==chs.length){
            res.add(sb.toString());
            return;
        }
        if (pos==chs.length){
            return;
        }
        for(int length=1;length<=3&&pos+length<=chs.length;length++){
            String str=s.substring(pos,pos+length);
            if(length<=2||Integer.parseInt(str)<=255){
                sb.append(count>0?"."+str:str);
                process(s,chs,count+1,pos+length,sb);
                int strLen=sb.length();
                sb.delete(count>0?strLen-length-1:strLen-length,strLen);
            }
            if(chs[pos]=='0'){
                return;
            }
        }
    }
}
